
package com.leetcode;

import java.util.Deque;
import java.util.LinkedList;

/**
 * Solution844
 */
public class Solution844 {

    public static void main(String[] args) {
        Solution844 s = new Solution844();
        String
                S = "y#fo##f",
                T = "y#f#o##f";
        System.out.println(s.backspaceCompare(S, T));
    }

    public boolean backspaceCompare(final String S, final String T) {

        Deque<Character> s = new LinkedList<>();
        Deque<Character> t = new LinkedList<>();

        for (char c : S.toCharArray()) {
            if (c == '#' ) {
                if (!s.isEmpty()) {
                    s.pop();
                }
            } else {
                s.push(c);
            }
        }
        for (char c : T.toCharArray()) {
            if (c == '#' ) {
                if (!t.isEmpty()) {
                    t.pop();
                }
            } else {
                t.push(c);
            }
        }

        if (s.size() != t.size()) {
            return false;
        }

        while (!s.isEmpty() && !t.isEmpty()) {
            if (s.pop() != t.pop()) {
                return false;
            }
        }


        return true;

    }
}